/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package topcoder;

import java.util.Arrays;
import java.util.List;

/**
 *
 * @author Mohamed.Azouz
 */
public class Mathematics {

    public boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        int m = (int) Math.sqrt(n);
        for (int i = 3; i < m; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void Sieve(int n) {
        int arr[] = new int[n + 1];
        Boolean prime[] = new Boolean[n + 1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = true;
        int m = (int) Math.sqrt(n + 1);
        for (int i = 2; i < m; i++) {
            if (prime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
        System.out.println(Arrays.toString(prime));
    }

    public static int GCD(int a, int b) {
        for (int i = Math.min(a, b); i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                return i;
            }
        }
        return -1;
    }

    public static int GCD_R(int a, int b) {
        if (b == 0) {
            return a;
        }
        return GCD_R(b, a % b);
    }

    public static int LCM(int a, int b) {
        return (b * a) / (GCD(a, b));
    }

    public static void main(String[] args) {
        //Sieve(100000);
        System.out.println(GCD(2336, 1314));;
        System.out.println(GCD_R(1314, 2336 ));;
        System.out.println(LCM(2336, 1314));;
    }
}
